In a digital signature scheme, a signer computes a pair of keys: a verification key and a matching signing key. The signer keeps this signing key secret and uses it in order to produce his digital signature (a string of bits) of a given message. The verification key is used by anyone who wishes to know whether a given string is the signer's digital signature of a message. Knowledge of the verification key alone is not, however, sufficient to produce correct signatures relative to the verification key. Thus, in order to enable as wide a distribution as possible for his own digital signature, the signer should make his verification key as public as possible. Therefore, verification keys are also referred to as "public keys" and signing keys are referred to as "secret keys".
Often, one needs to have a certain piece of data approved by two or more people or entities. This is easily accomplished by having each of such people or entities provide an individual digital signature of the data relative to his own public key. Using multiple signatures for the same data, however, can be quite wasteful, especially since one typically needs a certificate vouching that the corresponding public key really belongs to the correct user in order to verify each individual signature.
Techniques, such as threshold signatures, that are known in the prior art that may, in some contexts, reduce the size of multiple individual signatures. See, for example, Harn, "Group-oriented (t,n) threshold digital signature scheme and digital multisignature", IEE Proc.-Comput. Digit. Tech. Vol. 141, No. 5, 307-313 (Sept. 1994) and Gennaro et al., "Robust Threshold DSS Signatures", EuroCrypt 96.
While a Harn-type (t,n) threshold signature of data, D, vouches compactly for the fact that at least t out the n designated members approved D, it does not provide accountability of the at least t members who provided the necessary partial signatures of D. In fact, once the partial signatures of D are combined into a single signature of D relative to the combined public key, CPK (which is universally known or otherwise certified), it cannot be determined which signers approved D. The process of generating a signature of D relative to CPK is transparent to the verifier of the signature.
Because of the lack of accountability, producing a combined (t,n) threshold-signature of D relative to a given common key CPK is not, in many instances, a suitable method for signing D. Without accountability, t out of the n signers could provide partial signatures for false data and then deny, with impunity, having signed the false data.
A (t,n) threshold signature scheme keeps all the signers accountable when n=t. If an (n,n) threshold signature of D relative to CPK has been produced, then all n signers must have signed D, because all n signers must have contributed their own partial signatures of D. Therefore, none of the individual signatories can deny having signed the data. Unfortunately, however, in many cases an (n,n) threshold signature scheme is not practical. A large organization could have one hundred or more possible signers. It could therefore be impractical to require all of them sign each item of data produced by the organization.
It is thus desirable to develop a practical way to produce compact group signatures in a way that maintains accountability of the signers.